import java.util.Arrays;
import java.util.Stack;


public class Sort {
    //直接插入排序
    //时间复杂度:O(n^2)(最坏的情况)即,5 4 3 2 1
    //时间复杂度:O(n)(最好的情况)即,1 2 3 4 5
    //空间复杂度:O(1)
    //稳定性:稳定的排序
    public static void insertSort(int[] array){

        for(int i=1;i<array.length;i++){
            int temp=array[i];
            int j=i-1;
            for(;j>=0;j--){
                if(temp<array[j]){
                    array[j+1]=array[j];
                }else{
//                    array[j+1]=temp;
                    break;
                }
            }
            array[j+1]=temp;
        }
    }

    //希尔排序
    //希尔其实就是优化了的直接插入排序
    //时间复杂度:O(n^1.3)~O(n^1.5)
    //空间复杂度:O(1)
    public static void shellSort(int[] array){
        int gap=array.length;
        while(gap>1){
            gap/=2;
            shell(array,gap);
        }
    }
    public static void shell(int[] array,int gap){
        for(int i=gap;i<array.length;i++){
            int temp=array[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(temp<array[j]){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=temp;
        }
    }


    //选择排序
    //时间复杂度:O(n)
    //空间复杂度:O(1)
    public static void selectSort(int[] array){
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    //选择排序(同时找最大最小值)
    public static void selectSort1(int[] array){
        int left=0;
        int right=array.length-1;
        while(right>left){
            int minIndex=left;
            int maxIndex=right;
            for(int i=left+1;i<=right;i++){
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array, left, minIndex);
            //举个例子:15 3 7 2 6
            //15 和 6交换后：2 3 7 15 6
            //这里最大值就不是在下标为0的位置了
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array, right, maxIndex);
            left++;
            right--;
        }

    }
    public static void swap(int[] array,int i,int index){
        int temp=array[i];
        array[i]=array[index];
        array[index]=temp;
    }


    //堆排序
    public static void heapSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            shftDown(array,0,end);
            end--;
        }
    }
    public static void createHeap(int[] array){
        for(int parent=(array.length-1-1)/2;parent>=0;parent--){
            shftDown(array,parent,array.length);
        }
    }

    public static void shftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while(child<len){
            if(child+1<len&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }


    //冒泡排序
    //时间复杂度为:O(n^2)
    //空间复杂度为:O(1)
    public static void bubbleSort(int[] array){
        //i为趟数
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j+1]<array[j]){
                    swap(array,j,j+1);
                }
            }
        }
    }
    //优化冒泡排序
    public static void bubbleSort1(int[] array){
        //i为趟数
        for(int i=0;i<array.length-1;i++){
            boolean flag=false;
            for(int j=0;j<array.length-1-i;j++){
                if(array[j+1]<array[j]){
                    swap(array,j,j+1);
                    flag=true;
                }
            }
            //没交换过说明数组已经为有序的了,直接退出循环即可
            if(!flag){
                break;
            }
        }
    }


    //快速排序:
    //时间复杂度:O(n^2)(最差的情况:即单分支的时候,比如:5 4 3 2 1    1 2 3 4 5 )
    //一般都说是O(nlogn)
    //空间复杂度:最好的时候:O(logn)  最差的时候(单分支树):O(n)
    //稳定性:不稳定
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //par为划分的位置
        int par=partition1(array,left,right);
        //开始给右边的部分划分
        quick(array,par+1,right);
        //给左边的部分划分
        quick(array,left,par-1);
    }
    public static void quick1(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        //优化
        int index=midThreeNum(array,left,right);
        swap(array,index,left);
        //par为划分的位置,并且排序
        int par=partition1(array,left,right);
        //开始给右边的部分划分
        quick(array,par+1,right);
        //给左边的部分划分
        quick(array,left,par-1);
    }
    public static void quick2(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        if(right-left+1==7){
            insertSort(array,left,right);
            return;
        }
        //优化
        int index=midThreeNum(array,left,right);
        swap(array,index,left);
        //par为划分的位置
        int par=partition1(array,left,right);
        //开始给右边的部分划分
        quick(array,par+1,right);
        //给左边的部分划分
        quick(array,left,par-1);
    }
    //区间插入
    private static void insertSort(int[] array,int start,int end){
        for(int i=start+1;i<=end;i++){
            int temp=array[i];
            int j=i-1;
            for(;j>=start;j--){
                if(temp<array[j]){
                    array[j+1]=array[j];
                }else{
//                    array[j+1]=temp;
                    break;
                }
            }
            array[j+1]=temp;
        }
    }
    //找三位数的中位数(使其更接近于有序)
    public static int midThreeNum(int[] array,int start,int end){
        int mid=(start+end)/2;
        if(array[start]<array[end]){
            if(array[mid]>array[end]){
                return end;
            }else if(array[mid]<array[start]){
                return start;
            }else{
                return mid;
            }
        }else{
            if(array[mid]<array[end]){
                return end;
            }else if(array[mid]>array[start]){
                return start;
            }else{
                return mid;
            }
        }
    }
    public static int partition(int[] array,int start,int end){
        int i=start;
        int pivot=array[start];
        while(start<end){
            //注意前提条件:start<end,不然有可能越界
            //注意是先找比pivot小的,然后再找比pivot大的，顺序不能变
            while(start<end&&array[end]>=pivot){
                end--;
            }
            while(start<end&&array[start]<=pivot){
                start++;
            }
            //到这里array[end]比pivot小,array[start]比pivot大
            swap(array,start,end);
        }
        swap(array,i,start);
        return start;
    }
    //挖坑法(快排优化1)(更常用)
    public static int partition1(int[] array,int start,int end){
        int i=start;
        int pivot=array[start];
        while(start<end){
            while(start<end&&array[end]>=pivot){
                end--;
            }
            array[start]=array[end];
            while(start<end&&array[start]<=pivot){
                start++;
            }
            array[end]=array[start];
        }
        array[start]=pivot;
        return start;
    }
    //Hoare法(快排优化2)
    public static int partition2(int[] array,int left,int right) {
        int prev=left;
        int cur=left+1;
        while(cur<=right){
            while(array[cur]<array[left]&&array[++prev]!=array[cur]){
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }


    //非递归实现快速排序
    public static void quickSort3(int[] array){
        int left=0;
        int right=array.length-1;

        //划分
        int par=partition(array,left,right);
        Stack<Integer> stack=new Stack<>();
        if(par>left+1){
            stack.push(left);
            stack.push(par-1);
        }
        if(par<right-1){
            stack.push(par+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            //划分
             par=partition(array,left,right);
            if(par>left+1){
                stack.push(left);
                stack.push(par-1);
            }
            if(par<right-1){
                stack.push(par+1);
                stack.push(right);
            }

        }
    }


    //归并排序
    //时间复杂度:O(nlogn)
    //空间复杂度:O(n)
    //稳定性:稳定
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }
    public static void mergeSortFunc(int[] array,int left,int right){
        if(left==right){
            return;
        }
        int mid =(left+right)/2;
        //拆分
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        //合并
        merge(array,left,right,mid);
    }
    public static void merge(int[] array,int left,int right,int mid){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;

        int tmpArr[] = new int[right-left+1];
        int k=0;
        //排序核心代码
        while(s1<=e1&&s2<=e2){
            if(array[s1]<array[s2]){
                tmpArr[k++]=array[s1++];
            }else{
                tmpArr[k++]=array[s2++];
            }
        }
        //到这里一定有s1>e1或者s2>e2,把剩下的赋值到tmpArr数组里
        while(s1<=e1){
            tmpArr[k++]=array[s1++];
        }
        while(s2<=e2){
            tmpArr[k++]=array[s2++];
        }
        //然后赋值到原数组
        //注意+left,因为要考虑到mid的右边的情况，
        for(int i=0;i<tmpArr.length;i++){
            array[i+left]=tmpArr[i];
        }

    }

    //非递归实现归并排序
    public static void mergeSort1(int[] array){
        int gap=1;
        while(gap<= array.length){
            for(int i=0;i<array.length;i+=gap*2){
                int left=i;
                int mid = left+gap-1;
                int right = mid+gap;
                //防止越界,当left接近边界的时候，mid和right就容易越界
                if(mid>=array.length){
                    mid=array.length-1;
                }
                if(right>= array.length){
                    right=array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap*=2;
        }
    }


    //计数法排序
    //时间复杂度:O(范围(即最大最小值的差)+n)
    //空间复杂度:O(范围)
    //稳定性:稳定
    //要求数组元素集中在一定的范围内，如果像这种的数组就不适合:0 1 2 3 1000，跨度太大,浪费空间

    public static void countSort(int[] array){
        int maxNum=array[0];
        int minNum=array[0];
        //找出该数组的最大最小值
        for(int i=0;i<array.length;i++){
            if(array[i]>maxNum){
                maxNum=array[i];
            }
            if(array[i]<minNum){
                minNum=array[i];
            }
        }

        //最大最小值的差加一就是count的数组长度
        int len=maxNum-minNum+1;
        int[] count=new int[len];
        for(int i=0;i<array.length;i++){
            int index=array[i]-minNum;
            count[index]++;
        }

        //将count的下标赋值到原数组
        int k=0;
        for(int i=0;i<count.length;i++){
            while(count[i]!=0){
                array[k++]=i+minNum;
                count[i]--;
            }
        }

    }


    public static void main(String[] args) {
        int[] array={1,7,2,8,3,4,5,8,7,1,2};
//        insertSort(array);
//        System.out.println(Arrays.toString(array));

//        shellSort(array);
//        System.out.println(Arrays.toString(array));
//
//        selectSort(array);
//        System.out.println(Arrays.toString(array));

//        selectSort1(array);
//        System.out.println(Arrays.toString(array));

//        heapSort(array);
//        System.out.println(Arrays.toString(array));;

//        bubbleSort(array);
//        System.out.println(Arrays.toString(array));

//        quickSort3(array);
//        System.out.println(Arrays.toString(array));

//        mergeSort1(array);
//        System.out.println(Arrays.toString(array));;

        countSort(array);
        System.out.println(Arrays.toString(array));;
    }


}
